#include "Juego.h"
#include <cstdlib>
#include <iostream>
#include <string>
#include <stdlib.h>
#include <stdio.h>
#include <vector>
#include <list>
#include <map>
#include <climits>

using namespace std;

    
map <string,Juego*> mapjuegos;
    


void jugar(Juego * estado){
	int length = estado->numeros.size();
	string mapkey,maxMapKey;
	map<string,Juego*>::iterator it;
	int lado=0;
	int maxdiff = INT_MIN;
	int maxi;

	if (estado->turno != estado->actual){
		estado->cambiarJugadorActual();
		jugar(estado);
		if (!estado->finalizo()){
			jugar(estado);
			estado->turnoCount += 1 ;
		}
		return;
	}

	mapkey = estado->generateKey();
	if ( mapjuegos.count(mapkey) > 0  ){
		//cout << "SI matcheo " << mapkey << "\n";
		//cout << "actual " << estado->actual << " actual map" << mapjuegos[mapkey]->actual << "\n";
		
		if (estado->actual != mapjuegos[mapkey]->actual){
			*estado =  *(mapjuegos[mapkey]);
			estado->swapScores();	
		}else{
			*estado =  *(mapjuegos[mapkey]);
		}
			
		//cout << " matcheo " << mapkey << " | "<< estado->puntos[0] <<":"<<estado->puntos[1] << " actual map" << mapjuegos[mapkey]->actual << "\n";
		return;
	}
	//cout << "NO matcheo " << mapkey << "\n";
	//cout << "NO matcheo " << mapkey << " score " << estado->puntos[0] << " " << estado->puntos[1] << " actual " << estado->actual << "\n";
	if (length == 1){
		int v = 0;
		mapkey = estado->generateKey();
	//	cout << "registro " << mapkey << " | "<< estado->puntos[0] <<":"<<estado->puntos[1] << "\n";
		estado->addPuntos(estado->sum(1));
	//	cout << "registro " << mapkey << " | "<< estado->puntos[0] <<":"<<estado->puntos[1] << "\n";
		estado->numeros.pop_back();
		estado->turnoCount = 1;
		estado->pushMove(0,1);		
		mapjuegos[mapkey] = new Juego(estado);		
		return;
	}

	Juego * maxdiffJuego = new Juego();
	Juego * juegoderecha = new Juego();
	Juego * juegoizquierda = new Juego();

	int miJugador = estado->actual;
	int diffizq,diffder;
	int sumIzq,sumDer;
	//
	for(int i=1; i<= length ; i++){
		//
//		cout << "sum para length" << length << " "<< estado->sum(i) << "\n";
		*juegoizquierda = *estado;
		sumIzq = estado->sum(i);
		//juegoizquierda->addPuntos(estado->sum(i));
		juegoizquierda->extraer(i);
		juegoizquierda->pasarTurno();
		if (i != length)
			jugar(juegoizquierda);
		//
		*juegoderecha = *estado;
		sumDer = estado->sum(-i);
		//juegoderecha->addPuntos(estado->sum(-i));
		juegoderecha->extraer(-i);
		juegoderecha->pasarTurno();
		if (i != length)
			jugar(juegoderecha);
		//
		juegoizquierda->cambiarJugadorActual(miJugador);
		diffizq = sumIzq + juegoizquierda->getPuntos() - juegoizquierda->getPuntosOtro(); 
		//
		juegoderecha->cambiarJugadorActual(miJugador);
		diffder = sumDer + juegoderecha->getPuntos() - juegoderecha->getPuntosOtro();
		//
		if (maxdiff == INT_MAX or maxdiff < diffizq or maxdiff < diffder ){
			maxi = i;
			if (diffizq >= diffder){
				maxdiff = diffizq;
				lado = 0;
				*maxdiffJuego = *juegoizquierda;
				maxdiffJuego->addPuntos(sumIzq);
			}else{
				lado = 1;
				maxdiff = diffder;
				*maxdiffJuego = *juegoderecha;				
				maxdiffJuego->addPuntos(sumDer);
			}
			maxMapKey =  maxdiffJuego->generateKey();
			//cout << "-mapkey "<<mapkey<< " hija " << maxMapKey << " max i " << maxi << " lado " << lado << " der " ;
			//cout << sumDer << " izq " << sumIzq ;
			//cout << " puntos " << maxdiffJuego->puntos[0]<< " " << maxdiffJuego->puntos[1] << " actual " << estado->actual << "\n";
		}
	}
	*estado = *maxdiffJuego;
	estado->cambiarJugadorActual(miJugador);
	estado->turnoCount += 1 ;
	estado->pushMove(lado,maxi);
	mapjuegos[mapkey] = new Juego(estado);
	//cout << "===mapkey " << mapkey << " score " << estado->puntos[0] << " " << estado->puntos[1]<< " actual " << estado->actual << "\n";
}	



int main(int argc, char** argv) {
	char line[1000];
	int length = -1;
	vector<int> v;
	while ( cin.getline(line,50,' ') && line != "0" ){
		if(length == -1 ){
			length = atoi(line);
			v.resize(length);
			length = 0;
		}else{
			v[length] = atoi(line);
			length ++;
		}
	}
	Juego* j = new Juego(&v);
	// for(int i=0; i< v.size();i++)
	//	printf("%d/",v[i]);
	// printf("\n");
	//cout << *j;
	jugar(j);
	cout  << *j;
    return 0;
}


